GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Rucksackproblem</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Rucksackproblem</span></h1>

</header>

</div>

<p>Das <b>Rucksackproblem</b> (auch <span style="font-style:normal;font-weight:normal"><a href="Englische_Sprache" title="Englische Sprache">englisch</a></span> <span lang="en-Latn" style="font-style:italic"><i>knapsack problem</i></span>) ist ein <a href="Optimierungsproblem" title="Optimierungsproblem">Optimierungsproblem</a> der <a href="Kombinatorik" title="Kombinatorik">Kombinatorik</a>. Aus einer Menge von Objekten, die jeweils ein Gewicht und einen <a href="Nutzwert" title="Nutzwert">Nutzwert</a> haben, soll eine <a href="Teilmenge" title="Teilmenge">Teilmenge</a> ausgewählt werden, deren Gesamtgewicht eine vorgegebene Gewichtsschranke nicht überschreitet. Unter dieser Bedingung soll der Nutzwert der ausgewählten Objekte maximiert werden.

</p><p>Die Entscheidungsvariante des Rucksackproblems fragt, ob ein zusätzlich vorgegebener Nutzwert erreicht werden kann. Sie gehört zur Liste der <a href="Karps_21_NP-vollst%C3%A4ndige_Probleme" title="Karps 21 NP-vollständige Probleme">21 klassischen NP-vollständigen Probleme</a>, von denen <a href="Richard_M._Karp" title="Richard M. Karp">Richard Karp</a> 1972 die Zugehörigkeit zu dieser Klasse zeigen konnte.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p><p>In der <a href="Kryptographie" title="Kryptographie">Kryptographie</a> wird häufig eine andere Entscheidungsvariante betrachtet. Dabei werden nur die Gewichte betrachtet und es wird gefragt, ob es eine Teilmenge der Objekte gibt, die einen vorgegebenen Gewichtswert genau erreicht. Diese Problemvariante wird auch als <a href="Subset_Sum" class="mw-redirect" title="Subset Sum">SUBSET-SUM</a> bezeichnet. Basierend auf dieser Variante wurde das Public-Key-Kryptoverfahren <a href="Merkle-Hellman-Kryptosystem" title="Merkle-Hellman-Kryptosystem">Merkle-Hellman-Kryptosystem</a> entwickelt, das sich allerdings als nicht besonders sicher herausstellte.

</p>

<div class="mw-heading mw-heading2"><h2 id="Anschauung">Anschauung</h2></div>

<p>Das Rucksackproblem hat seinen Namen aus folgender Anschauung heraus erhalten: Es sind verschiedene Gegenstände mit einem bestimmten Gewicht und einem Nutzwert gegeben. Aus diesen Gegenständen soll nun eine Auswahl getroffen werden, die in einen Rucksack mit einer vorgegebenen Gewichtsschranke mitgenommen werden können. In der Literatur

wird zur Veranschaulichung auch gerne der Dieb herangezogen, der nur einen kleinen Teil der Beute im Rucksack abtransportieren kann und nun versucht, das Maximum an Nutzwert herauszuschlagen.

</p>

<div class="mw-heading mw-heading2"><h2 id="Mathematische_Formulierung">Mathematische Formulierung</h2></div>

<p>Gegeben ist eine <a href="Endliche_Menge" title="Endliche Menge">endliche Menge</a> von Objekten <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/458a728f53b9a0274f059cd695e067c430956025.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.783ex; height:2.176ex;" alt="{\displaystyle U}" loading="lazy"></span>. Durch eine Gewichtsfunktion <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy"></span> und die Nutzenfunktion <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"></span> wird den Objekten ein Gewicht und ein festgelegter Nutzwert zugeordnet:

</p>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w\colon U\rightarrow \mathbb {R} }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9c41d227a9773225c833c33ed980a39c12c3410d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.773ex; height:2.176ex;" alt="{\displaystyle w\colon U\rightarrow \mathbb {R} }" loading="lazy"></span></dd>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v\colon U\rightarrow \mathbb {R} }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a771abe76ede84f4119af593d88b072a2cc6f009.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.236ex; height:2.176ex;" alt="{\displaystyle v\colon U\rightarrow \mathbb {R} }" loading="lazy"></span></dd></dl>

<p>Des Weiteren gibt es eine vorgegebene Gewichtsschranke <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B\in \mathbb {R} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B\in \mathbb {R} }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0108be69edcbecc533d297833a09618624f78c08.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.283ex; height:2.176ex;" alt="{\displaystyle B\in \mathbb {R} }" loading="lazy"></span>.

</p><p>Gesucht ist eine Teilmenge <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K\subseteq U}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K\subseteq U}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/03e72a341c3ea869b7cd9a149f349b972a854a32.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.947ex; height:2.343ex;" alt="{\displaystyle K\subseteq U}" loading="lazy"></span>, die die Bedingung

</p>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{u\in K}w(u)\leq B}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/47c7ca504f06a3d9f394bbc5bfba428db23b6efa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:13.55ex; height:5.676ex;" alt="{\displaystyle \sum _{u\in K}w(u)\leq B}" loading="lazy"></span> einhält und die Zielfunktion <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum _{u\in K}v(u)}">

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{u\in K}v(u)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5840535f8294db8eeb00cd1da513020ec73f9d84.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:8.151ex; height:5.676ex;" alt="{\displaystyle \sum _{u\in K}v(u)}" loading="lazy"></span> maximiert.</dd></dl>

<p>Der Spezialfall <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v=w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v=w}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/06ca1941bc8772bcdcacdd30d281908336788729.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.89ex; height:1.676ex;" alt="{\displaystyle v=w}" loading="lazy"></span> führt auf das <a href="Teilsummenproblem" title="Teilsummenproblem">Teilsummenproblem</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Lösung_durch_dynamische_Programmierung"><span id="L.C3.B6sung_durch_dynamische_Programmierung"></span>Lösung durch dynamische Programmierung</h2></div>

<p>Sind die Gewichte ganzzahlig, so lässt sich der optimale Wert des Rucksackproblems auch mittels <a href="Dynamische_Programmierung" title="Dynamische Programmierung">dynamischer Programmierung</a> lösen. Seien dazu <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1,\ldots ,n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1,\ldots ,n}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/20d44d0ef6472db837c423f5bc86e0932eb9c288.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.735ex; height:2.509ex;" alt="{\displaystyle 1,\ldots ,n}" loading="lazy"></span> die Elemente von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/458a728f53b9a0274f059cd695e067c430956025.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.783ex; height:2.176ex;" alt="{\displaystyle U}" loading="lazy"></span>.

</p>

<div class="mw-highlight mw-highlight-lang-text mw-content-ltr mw-highlight-lines" dir="ltr"><pre><span></span><span class="linenos" data-line="1"></span>Eingabe: U, B, w, v wie oben beschrieben

<span class="linenos" data-line="2"></span> R := [1…(n+1), 0…B]-Matrix, mit Einträgen 0

<span class="linenos" data-line="3"></span> FOR i = n … 1

<span class="linenos" data-line="4"></span> FOR j = 1 … B

<span class="linenos" data-line="5"></span> IF w(i) <= j

<span class="linenos" data-line="6"></span> R[i,j] := max( v(i) + R[i+1, j-w(i)], R[i+1,j] )

<span class="linenos" data-line="7"></span> ELSE

<span class="linenos" data-line="8"></span> R[i,j] := R[i+1,j]

<span class="linenos" data-line="9"></span>Ausgabe: R[1,B]

</pre></div>

<p>In jeder Speicherzelle <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R(i,j)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R(i,j)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/063a40a7060a7792304bd9beb4e3c1a4d53f2c43.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.368ex; height:2.843ex;" alt="{\displaystyle R(i,j)}" loading="lazy"></span> ist der maximale Nutzwert bei maximal möglichem Gesamtgewicht von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy"></span> bei Berücksichtigung einer Teilmenge von Gegenständen aus der Teilsequenz <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [i..n]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [i..n]}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c55e2a0719f0575f4621405f4acc0756dc23e562.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.559ex; height:2.843ex;" alt="{\displaystyle [i..n]}" loading="lazy"></span> der Gesamtsequenz aller Gegenstände <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [1..n]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [1..n]}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1030b3f9fef008f8b2008a36db21a875a954ce86.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.145ex; height:2.843ex;" alt="{\displaystyle [1..n]}" loading="lazy"></span>. Also ist der maximale Nutzwert bei Berücksichtigung einer Teilmenge aller Gegenstände in der Zelle <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R(1,B)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R(1,B)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2cba52a936e8448db4bf20c7fa4fedbc16c4a330.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.534ex; height:2.843ex;" alt="{\displaystyle R(1,B)}" loading="lazy"></span> nach Beendigung des Algorithmus gespeichert.

</p><p>In jeder Zeile <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"></span> der Matrix <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"></span> wird über die beiden Fälle optimiert, ob der Nutzwert maximal vergrößert werden kann, wenn der Gegenstand <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"></span> mit dem Gewicht <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w(i)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w(i)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4ea948fa2f86d0af3cf84501b1d473dac1d0c5c0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.276ex; height:2.843ex;" alt="{\displaystyle w(i)}" loading="lazy"></span> dem Rucksack hinzugefügt oder er nicht aufgenommen wird. Im ersten Fall erhöht sich der Nutzwert um <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v(i)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v(i)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cfda7fed5f74a3fdef7021b10adc53b13a69a500.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.739ex; height:2.843ex;" alt="{\displaystyle v(i)}" loading="lazy"></span>.

</p><p>Um den Inhalt des Rucksacks mit dem maximalen Nutzwert zu bestimmen, kann er rekonstruiert werden, indem die Berechnung des Optimums in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R(1,B)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R(1,B)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2cba52a936e8448db4bf20c7fa4fedbc16c4a330.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.534ex; height:2.843ex;" alt="{\displaystyle R(1,B)}" loading="lazy"></span> mittels <a href="Backtracking" title="Backtracking">Backtracking</a> zurückverfolgt wird.

</p><p>Die Korrektheit folgt aus der folgenden Beobachtung:

</p><p>Sei <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K^{\star }}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K^{\star }}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/16c1d5c4024a1af0c4d2280c62b6949d9947ca03.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.148ex; height:2.343ex;" alt="{\displaystyle K^{\star }}" loading="lazy"></span> eine optimale Lösung. Dann ist <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K^{\star }\backslash \{i\}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K^{\star }\backslash \{i\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f1bf1504a0faccb8abf06eb02b3472b88d93e41c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.438ex; height:2.843ex;" alt="{\displaystyle K^{\star }\backslash \{i\}}" loading="lazy"></span> eine optimale Lösung für die Instanz <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U\backslash \{i\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U\backslash \{i\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6368ca4352540dec3aec8fd36aea9e21b81a5d2e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.072ex; height:2.843ex;" alt="{\displaystyle U\backslash \{i\}}" loading="lazy"></span> mit Maximalgewicht <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B-w(i)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B-w(i)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/819f72ffe514b25e8ef053cf57cc3537f2d4d13b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.88ex; height:2.843ex;" alt="{\displaystyle B-w(i)}" loading="lazy"></span>. Der Algorithmus benötigt aufgrund der verschachtelten <a href="For-Schleife" title="For-Schleife">for-Schleifen</a>, die über n und B iterieren, eine Laufzeit von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\cdot B)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\cdot B)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7f11b7de4425257ee0ab23f42a53e148f2ad5459.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.42ex; height:2.843ex;" alt="{\displaystyle O(n\cdot B)}" loading="lazy"></span>. Hierbei ist zu beachten, dass <i>B</i> eine zu seiner Eingabelänge exponentiell wachsende Größe und somit die Laufzeit <a href="Pseudopolynomiell" title="Pseudopolynomiell">pseudopolynomiell</a> ist.

</p>

<div class="mw-heading mw-heading2"><h2 id="Lösung_mittels_Profitabilitätsindex"><span id="L.C3.B6sung_mittels_Profitabilit.C3.A4tsindex"></span>Lösung mittels Profitabilitätsindex</h2></div>

<p>In der Praxis wird ein Ranking der Objekte nach Profitabilitätsindex vorgenommen:

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle PI=W\div R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle PI=W\div R}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/06b10e7da855e32b2cb9e4df3ba4c4958b0fc36a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:13.055ex; height:2.176ex;" alt="{\displaystyle PI=W\div R}" loading="lazy"></span>

</p>

<ul><li>PI = Profitabilitätsindex</li>

<li>W = Generierter Wert (hier: Nutzwert)</li>

<li>R = Verbrauchte Ressourcen (hier: Gewicht)</li></ul>

<p>Dann werden möglichst viele Objekte gewählt, beginnend mit dem Objekt mit höchstem Profitabilitätsindex. Dies führt bei ganzzahligen Problemen nicht immer zur optimalen Lösung, ist aber sehr praktikabel. Bei dieser Methodik handelt es sich um einen <a href="Greedy-Algorithmus" title="Greedy-Algorithmus">Greedy-Algorithmus</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Lösung_mittels_ganzzahliger_linearer_Optimierung"><span id="L.C3.B6sung_mittels_ganzzahliger_linearer_Optimierung"></span>Lösung mittels ganzzahliger linearer Optimierung</h2></div>

<p>Das Rucksackproblem lässt sich wie folgt als <a href="Ganzzahlige_lineare_Optimierung" title="Ganzzahlige lineare Optimierung">ganzzahliges lineares Optimierungsproblem</a> (<i>integer linear program</i> oder kurz <i>ILP)</i> formulieren. Sei dazu <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{u}\in \{0,1\}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{u}\in \{0,1\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1612e1026d43a45d4d33f423cca9e09a4d87628d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.836ex; height:2.843ex;" alt="{\displaystyle y_{u}\in \{0,1\}}" loading="lazy"></span> für jedes Element <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u\in U}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u\in U}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/65c3e0203fca1c3b6c1982520132b9f057ed5d88.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.953ex; height:2.176ex;" alt="{\displaystyle u\in U}" loading="lazy"></span> eine binäre Entscheidungsvariable mit der folgenden Interpretation:

</p>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{u}=1}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bbfbe34ea9fc4f57353359ade6fdb83f5e7249be.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.573ex; height:2.509ex;" alt="{\displaystyle y_{u}=1}" loading="lazy"></span>: Das Element <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" loading="lazy"></span> wird im Rucksack mitgenommen.</li>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{u}=0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cda1f43c897c8bf001ff1457cda6fdc541ae4f28.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.573ex; height:2.509ex;" alt="{\displaystyle y_{u}=0}" loading="lazy"></span>: Das Element <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" loading="lazy"></span> wird nicht im Rucksack mitgenommen.</li></ul>

<p>Dies führt zu folgender Modellierung des Rucksackproblems

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ILP:\qquad \max _{y}\sum _{u\in U}v(u)y_{u}\quad {\text{s. t.}}\quad \sum _{u\in U}w(u)y_{u}\leq B,\ y_{u}\in \{0,1\},\ u\in U}">

</mrow>

</munder>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ILP:\qquad \max _{y}\sum _{u\in U}v(u)y_{u}\quad {\text{s. t.}}\quad \sum _{u\in U}w(u)y_{u}\leq B,\ y_{u}\in \{0,1\},\ u\in U}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/381597e7ff65776c3940810dc6e0766cb4e4b501.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:70.581ex; height:5.676ex;" alt="{\displaystyle ILP:\qquad \max _{y}\sum _{u\in U}v(u)y_{u}\quad {\text{s. t.}}\quad \sum _{u\in U}w(u)y_{u}\leq B,\ y_{u}\in \{0,1\},\ u\in U}" loading="lazy"></span>,

</p><p>welches mit gängigen kommerziellen und nichtkommerziellen Solvern wie etwa <a href="CPLEX" title="CPLEX">CPLEX</a>, <a href="Gurobi" title="Gurobi">Gurobi</a>, FICO Xpress, SCIP, <a href="GLPK" class="mw-redirect" title="GLPK">GLPK</a> und CBC auch für große praxisrelevante Instanzen global optimal gelöst werden kann.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Anwendungen">Anwendungen</h2></div>

<p>Viele reale Situationen lassen sich mit Hilfe der Lösung dieses Problems mathematisch klären. Oft steht eine begrenzte Kapazität zur Verfügung, welche nicht die gesamte Nachfrage befriedigen kann. Man denke z. B. an einen Lkw, der viele verschiedene Güter – mit einem bestimmten Gewinn – transportieren soll, aber wegen der begrenzten Lademenge nicht alle Güter aufnehmen kann. Der Besitzer des Lkws wird die Ladung so wählen wollen, dass der Gewinn maximal ausfällt.

</p>

<div class="mw-heading mw-heading2"><h2 id="Siehe_auch">Siehe auch</h2></div>

<ul><li><a href="Greedy-Algorithmus" title="Greedy-Algorithmus">Greedy-Algorithmus</a></li>

<li><a href="Optimierungsproblem" title="Optimierungsproblem">Optimierungsproblem</a></li>

<li><a href="Teilsummenproblem" title="Teilsummenproblem">Teilsummenproblem</a></li>

<li><a href="Partitionsproblem" title="Partitionsproblem">Partitionsproblem</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li><a href="Hans_Kellerer" title="Hans Kellerer">Hans Kellerer</a>, Ulrich Pferschy, David Pisinger: <cite style="font-style:italic">Knapsack Problems</cite>. Springer, Berlin u. a. 2004, ISBN 3-540-40286-1.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Rucksackproblem&rft.au=Hans+Kellerer%2C+Ulrich+Pferschy%2C+David+Pisinger&rft.btitle=Knapsack+Problems&rft.date=2004&rft.genre=book&rft.isbn=3540402861&rft.place=Berlin+u.+a.&rft.pub=Springer" style="display:none"> </span></li>

<li>Silvano Martello, Paolo Toth: <cite style="font-style:italic">Knapsack problems. Algorithms and computer implementations</cite>. J. Wiley, Chichester u. a. 1990, ISBN 0-471-92420-2 (<a rel="nofollow" class="external text" href="http://www.or.deis.unibo.it/knapsack.html">Buch als PDF und Fortran-Quelltext zum Buch</a>).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Rucksackproblem&rft.au=Silvano+Martello%2C+Paolo+Toth&rft.btitle=Knapsack+problems.+Algorithms+and+computer+implementations&rft.date=1990&rft.genre=book&rft.isbn=0471924202&rft.place=Chichester+u.+a.&rft.pub=J.+Wiley" style="display:none"> </span></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://www.proggen.org/doku.php?id=algo:knapsack">Das Rucksackproblem (Knapsack Problem)</a> – Ausführliche Erklärung mit Grafiken und Beispiel-Implementierung</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text">Richard M.Karp: <cite class="lang" lang="en-US" dir="auto" style="font-style:italic">Reducibility Among Combinatorial Problems</cite>. In: Springer (Hrsg.): <cite class="lang" lang="en-US" dir="auto" style="font-style:italic">Proceedings of a symposium on the Complexity of Computer Computations</cite>. Yorktown Heights, New York 1972, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>85–103</span> (amerikanisches Englisch, <a rel="nofollow" class="external text" href="https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9">springer.com</a>).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Rucksackproblem&rft.atitle=Reducibility+Among+Combinatorial+Problems&rft.au=Richard+M.Karp&rft.btitle=Proceedings+of+a+symposium+on+the+Complexity+of+Computer+Computations&rft.date=1972&rft.genre=book&rft.pages=85-103&rft.place=Yorktown+Heights%2C+New+York" style="display:none"> </span></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><a href="#cite_ref-2">↑</a></span> <span class="reference-text">David Pisinger: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Where are the hard knapsack problems?</cite> In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Computers & Operations Research</cite>. <span style="white-space:nowrap">Band<span style="display:inline-block;width:.2em"> </span>32</span>, <span style="white-space:nowrap">Nr.<span style="display:inline-block;width:.2em"> </span>9</span>, September 2005, <a href="Internationale_Standardnummer_f%C3%BCr_fortlaufende_Sammelwerke" title="Internationale Standardnummer für fortlaufende Sammelwerke">ISSN</a> <span style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://zdb-katalog.de/list.xhtml?t=iss%3D%220305-0548%22&key=cql">0305-0548</a></span>, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>2271–2284</span>, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1016/j.cor.2004.03.002">10.1016/j.cor.2004.03.002</a></span> (englisch, <a rel="nofollow" class="external text" href="https://www.dcs.gla.ac.uk/~pat/cpM/jchoco/knapsack/papers/hardInstances.pdf">gla.ac.uk</a> [PDF; abgerufen am 4. Dezember 2023]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Rucksackproblem&rft.atitle=Where+are+the+hard+knapsack+problems%3F&rft.au=David+Pisinger&rft.date=2005-09&rft.doi=10.1016%2Fj.cor.2004.03.002&rft.genre=journal&rft.issn=0305-0548&rft.issue=9&rft.jtitle=Computers+%26+Operations+Research&rft.pages=2271-2284&rft.volume=32" style="display:none"> </span></span>

</li>

</ol>

/* start https://de.wikipedia.org/ */

.mw-parser-output div.klappleiste{border:1px solid var(--dewiki-rahmenfarbe1);clear:both;font-size:95%;box-sizing:border-box;margin-top:1.5em;padding:2px}.mw-parser-output div.klappleiste:after{clear:both;content:"";display:block}.mw-parser-output div.klappleiste-bild{float:left;padding:2px}.mw-parser-output div.klappleiste-kopf{background:var(--dewiki-hintergrundfarbe5);color:var(--color-base,#202122);text-align:center;font-weight:bold}.mw-parser-output div.klappleiste.mw-collapsed .klappleiste-bild{display:none}.mw-parser-output div.klappleiste+div.klappleiste,.mw-parser-output div.klappleiste+link+div.klappleiste,.mw-parser-output div.klappleiste+link+link+div.klappleiste,.mw-parser-output div.klappleiste+link+style+div.klappleiste,.mw-parser-output div.klappleiste+style+div.klappleiste,.mw-parser-output div.klappleiste+style+style+div.klappleiste,.mw-parser-output div.klappleiste+style+link+div.klappleiste{margin-top:-1px}@media screen{html.skin-theme-clientpref-night .mw-parser-output .klappleiste-bild span[typeof="mw:File"]:not(.skin-invert-image) img{background-color:#c8ccd1}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .klappleiste-bild span[typeof="mw:File"]:not(.skin-invert-image) img{background-color:#c8ccd1}}

/* end https://de.wikipedia.org/ */

</style>

<div class="klappleiste-kopf"><a href="Karps_21_NP-vollst%C3%A4ndige_Probleme" title="Karps 21 NP-vollständige Probleme">Karps 21 NP-vollständige Probleme</a></div>

<p><a href="Erf%C3%BCllbarkeitsproblem_der_Aussagenlogik" title="Erfüllbarkeitsproblem der Aussagenlogik">Erfüllbarkeitsproblem der Aussagenlogik</a> |

<a href="Cliquenproblem" title="Cliquenproblem">Cliquenproblem</a> |

<a href="Mengenpackungsproblem" title="Mengenpackungsproblem">Mengenpackungsproblem</a> |

<a href="Knoten%C3%BCberdeckungsproblem" class="mw-redirect" title="Knotenüberdeckungsproblem">Knotenüberdeckungsproblem</a> |

<a href="Mengen%C3%BCberdeckungsproblem" title="Mengenüberdeckungsproblem">Mengenüberdeckungsproblem</a> |

<a href="Feedback_Arc_Set" title="Feedback Arc Set">Feedback Arc Set</a> |

<a href="Feedback_Vertex_Set" title="Feedback Vertex Set">Feedback Vertex Set</a> |

<a href="Hamiltonkreisproblem" title="Hamiltonkreisproblem">Hamiltonkreisproblem</a> |

<a href="Ganzzahlige_lineare_Optimierung#0.2F1-Programmierung" title="Ganzzahlige lineare Optimierung">Integer Linear Programming</a> |

<a href="3-SAT" title="3-SAT">3-SAT</a> |

<a href="F%C3%A4rbung_(Graphentheorie)" title="Färbung (Graphentheorie)">graph coloring problem</a> |

Covering by cliques |

<a href="Problem_der_exakten_%C3%9Cberdeckung" title="Problem der exakten Überdeckung">Problem der exakten Überdeckung</a> |

3-dimensional matching |

<a href="Steinerbaumproblem" title="Steinerbaumproblem">Steinerbaumproblem</a> |

<a href="Hitting-Set-Problem" title="Hitting-Set-Problem">Hitting set</a> |

<a class="mw-selflink selflink">Rucksackproblem</a> |

Job sequencing |

<a href="Partitionsproblem" title="Partitionsproblem">Partitionsproblem</a> |

<a href="Maximaler_Schnitt" title="Maximaler Schnitt">Maximaler Schnitt</a>

</p>

</div></div></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-11-30" href="https://de.wikipedia.org/wiki/?title=Rucksackproblem&oldid=262000956">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>